# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: bucket.py
@time: 2022/7/25 21:34
@author: LDC
"""
'''
6、桶排序 (Bucket sort)
或所谓的箱排序，顾名思义就是运用桶的思想来将数据放到相应的桶内，
再将每一个桶内的数据进行排序，
最后把所有桶内数据按照顺序取出来，得到的就是我们需要的有序数据
'''
import random
import time


def bucketSort(list1):
    maxNum = max(list1)
    minNum = min(list1)
    bucket = [0] * (maxNum - minNum + 1)  # 创建一个桶列表，长度为要排序的列表中最大的数与最小的数的差加1
    for i in list1:
        bucket[i - minNum] += 1  # 把要排序的列表中的元素放到相应下标的桶中
    list2 = []
    for i in range(len(bucket)):  # 遍历桶列表，输出排序好的新列表
        if bucket[i] != 0:
            list2 += [i + minNum] * bucket[i]  # 对桶列表中的元素进行计数，有几个就加几个相同的元素
    return list2


if __name__ == '__main__':
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    list2 = bucketSort(list1)
    end1 = time.perf_counter()
    print("桶排序        ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list2 == list4)
